package com.caoyanan.algorithm.question.zuoTraining.training004.class05;

import java.util.Comparator;
import java.util.Objects;
import java.util.TreeSet;

/**
 *
 * 给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。再给定一个正数 limit，代表一艘船的载重。
 * 以下是坐船规则，
 * 1)每艘船最多只能做两人;
 * 2)乘客 的体重和不能超过limit
 * 返回如果同时让这N个人过河最少需要几条船。
 *
 * // java有序表 -> 红黑树
 * 		// 有序表 ： 跳表、AVL树、SB树...
 * 		// 只是底层细节不一样，但是对外提供的接口，和每个接口的性能都一样
 * 		// O(logN)
 * 		// 哈希表：O(1)
 * 	而大顶堆和小顶堆也是一个有序的结构，但是仅仅提供 add,poll操作
 *
 * @author: caoyanan
 * @time: 2021/6/21 21:20
 */
public class Question03_HowManyBoatsCrossTheRiver {

    public static void main(String[] args) {

        int[] arr = { 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5 };
        int weight = 6;
        System.out.println(minBoat(arr, weight));
    }

    private static int minBoat(int[] arr, int limit) {
        TreeSet<Node> set = new TreeSet<Node>(new NodeComparator());
        for (int i = 0; i < arr.length; i++) {
            set.add(new Node(arr[i]));
        }
        int count = 0;
        while (!set.isEmpty()) {
            Node node = set.pollLast();
            Node together = set.floor(new Node(limit - node.v));
            if (Objects.nonNull(together)) {
                set.remove(together);
            }
            count++;
        }

        return count;
    }

    public static class NodeComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            if (o1.v == o2.v) {
                return o1.hashCode() - o2.hashCode();
            }
            return o1.v - o2.v;
        }
    }
    public static class Node {
        public int v;
        public Node(int v) {
            this.v = v;
        }
    }
}
